Three dimensional (3D) displays add a third dimension to the viewing experience by providing a viewer's two eyes with different views of the scene being watched. This can be achieved by having the user wear glasses to separate two views that are displayed. However, as this may be considered inconvenient to the user, it is in many scenarios preferred to use autostereoscopic displays that use means at the display (such as lenticular lenses, or barriers) to separate views, and to send them in different directions where they individually may reach the user's eyes. For stereo displays, two views are required whereas autostereoscopic displays typically require more views (such as e.g. nine views).
In order to implement 3D functionality, it is important that an effective representation and processing of three dimensional information can be employed. One widely used approach is to represent the three dimensional information by three dimensional objects which can be processed and manipulated by suitable algorithms.
A particularly effective approach in many scenarios is to represent image objects by a polygon mesh where a set of polygons are connected by their common edges or corners, which are given by three dimensional positions. The combined three dimensional polygon mesh accordingly provides an effective model of three dimensional objects, including possibly a three dimensional description of an entire image. The polygon mesh is often a triangle mesh formed by triangles having common corners given in 3D space.
In such representations, the polygon mesh is used to provide information of the three dimensional geometry of the object whereas the texture is typically provided as a separate data structure. Specifically, the texture is often provided as a separate two dimensional map which by the processing algorithm can be overlaid on the three dimensional geometry.
The use of triangle meshes is particularly suitable for processing and manipulation by computer graphics algorithms, and many efficient software and hardware solutions have been developed and are available in the market. A substantial computational efficiency is in many of the systems achieved by the algorithm processing the individual vertices commonly for a plurality of polygons rather than processing each polygon separately. For example, for a typical triangle mesh, the individual vertex is often common to several (often 3-8) triangles. The processing of a single vertex may accordingly be applicable to a relatively high number of triangles thereby substantially reducing the number of points in an image or other object that is being processed.
As a specific example, many current Systems on Chip (SoCs) contain a Graphics Processing Unit (GPU) which is highly optimized for processing of 3D graphics. For instance, the processing of 3D object geometry and 3D object texture is done using two largely separate paths in the so called OpenGL rendering pipeline (or in many other APIs such as DirectX). The hardware of GPUs on SoCs can deal efficiently with 3D graphics as long as the 3D source is presented to the GPU in the form of vertices (typically of triangles) and textures. The OpenGL application interface then allows setting and control of a virtual perspective camera that determines how 3D objects appear as projected on the 2D screen. Although OpenGL uses 3D objects as input, the output is typically a 2D image on a normal 2D display.
However, whereas such approaches are attractive in many scenarios, it requires that the three dimensional information is provided by a polygon mesh and associated texture information. However, in many applications three dimensional image data may be provided in different formats, such as for example by an image and a depth map.
Indeed, a widely used 3D format is video with a depth map that is typically produced in post-production, estimated from stereo video, or captured using a depth camera. Another frequently used 3D format is using stereo images corresponding to the left and right eye views. Such frequently used formats do not contain static objects represented by polygons and textures.
For such applications, it is therefore desirable to perform a conversion of the video plus depth (or stereo image) format to a format that consists of a polygon mesh and texture image which would be directly suitable for playback using e.g. the openGL algorithms.
However, such conversion is far from trivial and poses a number of complex problems and challenges. Specifically, in order to convert an image with depth map (or stereo images) to geometry (represented by a polygon mesh) and texture it is necessary to convert the depth map to a set of polygons with vertices where each vertex has an x, y and z coordinate. Furthermore, the conversion is typically able to determine the so-called u,v-texture coordinates that specify where each vertex maps onto the video texture. These (u,v) parameters can e.g. be derived from a (x,y) parameters using a projection matrix, or vice versa.
There are different ways known for performing such a conversion into a polygon map. In many applications, preferred properties of the conversion include:                Polygons should form a mesh where each u,v-texture coordinate maps into a unique location on the 3D polygon mesh.        The mesh should be contiguous without any holes.        Polygons should accurately model the depth map.        The number of polygons should be small to limit GPU load;        The algorithm for extracting polygons from the depth map should be low-complexity;        Preferably the conversion can be performed at the client side or at the server side.        
However, known algorithms for generating a polygon mesh from an image tend to be suboptimal and suffer from imperfections. Hence, an improved approach for generating a triangle mesh for a three dimensional image would be advantageous and in particular an approach that allows increased flexibility, increased accuracy, a more consistent and/or contiguous triangle mesh, reduced complexity, improved computational efficiency, a representation suitable for subsequent graphics processing, increased compatibility with existing approaches for graphics processing and/or improved performance would be advantageous.